package sys.cloud.demo.datastructure.link;

/**
 * Created by shiyusen on 2017/3/21.
 */
public class LinkedListSummary {
    static Node head=new Node(0);
    static Node curr=head;
    static {
        for(int i=1;i<10;i++){
            Node node=new Node(i);
            curr.next=node;
            curr=node;
        }
    }

    public static void main(String[] args) {
//        int c=getListLength(head);
//        System.out.println(c);
//        print(head);
//        Node new_head=reverseList(head);
        print(reGetKthNode(head,1));
    }
    public static void print(Node head){
        System.out.println("--------------start-------------------");
        while(head!=null){
            System.out.print(head.value+"\t");
            head=head.next;
        }
        System.out.println("\n--------------end-------------------");
    }

    //查找单链表中的倒数第K个结点（k > 0）
    public static Node reGetKthNode(Node head,int k){
        int c=getListLength(head);
        int index=0;
        while(head!=null){
            if(index+k==c){
                return head;
            }
            head=head.next;
            index++;
        }
        return head;
    }
        //将单链表反转,递归
    public static Node reverseListRec(Node head){
        if(head==null||head.next==null)return head;
        Node reHead=reverseListRec(head.next);
        head.next.next=head;
        head.next=null;
        return reHead;
    }
    /**
     * 循环的方式，将单链表反转。
     * 原理：讲当前节点的next指向上一个节点pre（转向），前提是先备份next
     * 然后，将上一个节点pre重置为当前节点，讲当前节点head重置为next，开始新的循环
     * @param head 当前节点/头节点
     * @return
     */
    public static Node reverseList(Node head){
        //缓存当前节点的前后节点
        Node pre=null;
        Node next=null;
        while(null!=head){
            //记录当前节点的下一个节点
            next=head.next;
            //讲当前节点的next指向上一个节点pre
            head.next=pre;
            //将上一个节点pre重置为当前节点
            pre=head;
            //讲当前节点head重置为next
            head=next;

        }
        return pre;
    }

    /**
     * 求单链表中结点的个数: getListLength
     * 这是最最基本的了，应该能够迅速写出正确的代码，注意检查链表是否为空。时间复杂度为O（n）。参考代码如下：
     * @param head
     * @return
     */
    public static int getListLength(Node head){
        int c=0;
        while(head!=null){
            c++;
            head=head.next;
        }
        return c;
    }

    public static class Node{
        int value;
        Node next;
        public Node(int n){
            this.value=n;
            this.next=null;
        }
    }
}
